#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <string>
#include <sstream>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> nums(n,0);
		vector<string> result;
		solve(0,0,nums,result);
		return result;
    }

	void solve(int curIdx,int preSum,vector<int>& nums,vector<string>& result)
	{
		if(curIdx == (nums.size()-1))
		{
			int n = nums.size();
			nums[n-1] = n-preSum;
			ostringstream oss;
			for(size_t i=0;i<nums.size();i++)
			{
				oss<<"(";
				for(int j=0;j<nums[i];j++)
				{
					oss<<")";
				}
			}
			result.push_back(oss.str());
			return;
		}
		int left = curIdx+1-preSum;
		for(int i=0;i<=left;i++)
		{
			nums[curIdx] = i;
			solve(curIdx+1,preSum+i,nums,result);
		}
	}
};
#endif